import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 查找算法之一：二分法查找算法
 *      适用于在一个有序数组中，查找某个数
 */
public class BinarySearch {
    public static void main(String[] args) {
        //必须是一个有序数组
        int[] ints = {1, 8, 10, 89, 1000, 1000, 1000, 1234};
        //调用线性查找算法
//        int i = binarySearch(ints, 100, 0, ints.length);
        int i = binarySearch2(ints, 89);

        //根据返回值，处理查询结果
        if (i != -1) {
            System.out.println("查询值的下标是：" + i);
        } else {
            System.out.println("数组中没有这个值！");
        }
        System.out.println("-----------------------");

        // 对多个相同值的查找
        ArrayList<Integer> integers = binarySearchUpgrade(ints, 1000, 0, ints.length);
        System.out.println(integers);
    }

    //二分法查找算法：递归实现
    public static int binarySearch(int[] arr,int value,int left,int right){
        //先找到中间值的索引
        int mid = (left + right) / 2;
        //获取中间值
        int midVal = arr[mid];
        //若左边界大于右边界了，则表示数组中不存在查找的这个数，可以结束递归方法调用了
        if (left > right) {
            return -1;
        }
        //根据具体情况进行查询
        if (value < midVal) {
            //若查找值小于中间值，则向左递归查询，右边界在不断缩小
            return binarySearch(arr,value,left,mid-1);
        }else if (value > midVal){
            //若查找值大于中间值，则向右递归查询，左边界在不断缩小
            return binarySearch(arr,value,mid+1,right);
        }else{
            //若查找值=中间值，则直接返回中间值索引
            return mid;
        }
    }

    // 对多个相同值的查找
    // 思路分析 在找到mid的时候不要马上返回 向mid的索引的左/右边扫描  将所有满足的查找值1000的所有下标 放入数组中
    public static ArrayList<Integer> binarySearchUpgrade(int[] arr, int value, int left, int right){
        //先找到中间值的索引
        int mid = (left + right) / 2;
        //获取中间值
        int midVal = arr[mid];
        //创建一个集合，接收多个相同值的下标
        ArrayList<Integer> list = new ArrayList<>();
        //若左边界大于右边界了，则表示数组中不存在查找的这个数，可以结束递归方法调用了
        if (left > right) {
            return list;
        }
        //根据具体情况进行查询
        if (value < midVal) {
            //若查找值小于中间值，则向左递归查询，右边界在不断缩小
            return binarySearchUpgrade(arr,value,left,mid-1);
        }else if (value > midVal){
            //若查找值大于中间值，则向右递归查询，左边界在不断缩小
            return binarySearchUpgrade(arr,value,mid+1,right);
        }else{
            //若查找值=中间值，先不返回
            int temp = mid;
            //向左扫描,若发现有相同值，则将下标添加进集合中去
            while (midVal == arr[--temp]){
                list.add(temp);
            }
            //本来的中值添加进去
            list.add(mid);
            //将temp重新回归到初始的中值位置，再向右扫描
            temp = mid;
            //向右扫描，若发现有相同值，则将下标添加进集合中去
            while (midVal == arr[++temp]){
                list.add(temp);
            }
            return list;
        }
    }

    //二分法查找算法：循环实现
    public static int binarySearch2(int[] arr,int value){
        //定义头索引
        int head = 0;
        //定义尾索引
        int end = arr.length-1;
        //定义中值索引
        int mid = 0;
        //定义一个标记
        boolean flag = false;
        while (head <= end){
            mid = (head + end) / 2;
            if (value == arr[mid]) {
                flag = true;
                break;
            }else if (value > arr[mid]){
                head = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        if (flag) {
            return mid;
        }else {
            return -1;
        }
    }
}
